package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/generate-parentheses/
 */
public class 括号生成_22 {

    public static void main(String[] args) {

    }

    /**
     * 回溯+剪枝
     * 1，生成 n 对括号，那么也就是说需要填 2*n 个字符，每个字符
     * 可能是 ( 或者 )
     * 2，需要是有效的括号需要满足的条件
     * a. 恰好有 n 个 ( 和 n 个 )
     * b. 递归过程中，保证 ) 个数 <= ( 的个数
     */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();

        dfs(new StringBuilder(), 0, 0, n, list);

        return list;
    }

    private void dfs(StringBuilder stringBuilder, int lCnt, int rCnt, int n, List<String> list) {
        if (lCnt > n || rCnt > n) return;
        if (rCnt > lCnt) return;
        if (lCnt == n && rCnt == n) {
            list.add(stringBuilder.toString());
            return;
        }

        stringBuilder.append("(");
        dfs(stringBuilder, lCnt + 1, rCnt, n, list);
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);

        stringBuilder.append(")");
        dfs(stringBuilder, lCnt, rCnt + 1, n, list);
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
    }

}
